class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: 'List[str]') -> int:
        # Reference: https://blog.csdn.net/qq_17550379/article/details/83652490
        # 广度优先搜索
        if  not endWord in wordList:
            return 0
        if beginWord in wordList:
            wordList.remove(beginWord)
        wordDict = dict()
        for word in wordList:
            for i in range(len(word)):
                tmp = word[:i] + "_" + word[i+1:]
                wordDict[tmp] = wordDict.get(tmp, []) + [word]

        stack, visited = [(beginWord, 1)], set()
        while stack:
            word, step = stack.pop(0)
            if word not in visited:
                visited.add(word)
                if word == endWord:
                    return step
                for i in range(len(word)):
                    tmp = word[:i] +'_' + word[i+1:]
                    neigh_words = wordDict.get(tmp, [])
                    for neigh in neigh_words:
                        if neigh not in visited:
                            stack.append((neigh, step + 1))
        return 0

